/**
 * 
 */
package algorithm;

import java.util.ArrayList;

/**
 * @author xyyi
 *
 */
public class PascalTriangle {

	/*
	Pascal Triangle 
	
	
	Given numRows, generate the first numRows of Pascal's triangle.

	For example, given numRows = 5,
	Return 
	
	
	[
	     [1],
	    [1,1],
	   [1,2,1],
	  [1,3,3,1],
	 [1,4,6,4,1]
	]
	*/
	public ArrayList<ArrayList<Integer>> generate(int numRows) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

		if (numRows <= 0)
			return result;

		for (int row = 0; row < numRows; row++) {
			ArrayList<Integer> curr = new ArrayList<Integer>();
			ArrayList<Integer> last = row == 0 ? null : result.get(row - 1);
			for (int col = 0; col <= row; col++) {
				if (col == 0 || col == row) {
					curr.add(1);
				} else {
					curr.add(last.get(col - 1) + last.get(col));
				}
			}
			result.add(curr);
		}

		return result;
	}

	/*
	 Pascal's Triangle II
	 Oct 29 '12

		Given an index k, return the kth row of the Pascal's triangle.
		
		For example, given k = 3,
		Return [1,3,3,1].
		
		Note:
		Could you optimize your algorithm to use only O(k) extra space? 
	 */
	public ArrayList<Integer> getRow(int rowIndex) {
		ArrayList<Integer> curr = new ArrayList<Integer>();
		if (rowIndex < 0)
			return curr;

		ArrayList<Integer> last = new ArrayList<Integer>();
		for (int row = 0; row <= rowIndex; row++) {
			for (int col = 0; col <= row; col++) {
				if (col == 0 || col == row) {
					curr.add(1);
				} else {
					curr.add(last.get(col - 1) + last.get(col));
				}
			}
			ArrayList<Integer> temp = curr;
			curr = last;
			last = temp;
			curr.clear();
		}

		return last;
	}

	/**
	 * 
	 */
	public PascalTriangle() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
